let widthTraversal = (node) => {
  let nodes = []
  let stack = []
  if (node) {
    stack.push(node)
    while (stack.length) {
      let item = stack.shift()
      let children = item.children
      nodes.push(item)
      // 队列，先进先出
      // nodes = [] stack = [parent]
      // nodes = [parent] stack = [child1,child2,child3]
      // nodes = [parent, child1] stack = [child2,child3,child1-1,child1-2]
      // nodes = [parent,child1,child2]
      for (let i = 0; i < children.length; i++) {
        stack.push(children[i])
      }
    }
  }
  return nodes
}

/**
 * 二叉树广度遍历
 */
var tree = {
  value: "-",
  left: {
    value: '+',
    left: {
      value: 'a',
    },
    right: {
      value: '*',
      left: {
        value: 'b',
      },
      right: {
        value: 'c',
      }
    }
  },
  right: {
    value: '/',
    left: {
      value: 'd',
    },
    right: {
      value: 'e',
    }
  }
}
let result = [];
let stack = [tree]; // 先将要遍历的树压入栈
let count = 0; // 用来记录执行到第一层
let bfs = function () {
  let node = stack[count];
  if (node) {
    result.push(node.value);
    if (node.left) stack.push(node.left);
    if (node.right) stack.push(node.right);
    count++;
    bfs();
  }
}
dfc();
console.log(result);
//  ["-", "+", "/", "a", "*", "d", "e", "b", "c"]

// 非递归
function bfs2(node) {
  let result = [];
  let queue = [];
  queue.push(node);
  let pointer = 0;
  while (pointer < queue.length) {
    let node = queue[pointer++]; // // 这里不使用 shift 方法（复杂度高），用一个指针代替
    result.push(node.value);
    node.left && queue.push(node.left);
    node.right && queue.push(node.right);
  }
  return result;
}

bfs2(tree);